import functools

class Solution(object):
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        if len(nums)<4:return []
        nums.sort()
        results = []
        for a in range(0, len(nums)-3):
            sa = nums[a]
            if sa+nums[a+1]+nums[a+2]+nums[a+3]>target:break
            if sa+nums[-1]+nums[-2]+nums[-3]<target:continue
            for b in range(a+1, len(nums)-2):
                sab = sa+nums[b]
                if sab+nums[b+1]+nums[b+2]>target:break
                if sab+nums[-1]+nums[-2]<target:continue
                for c in range(b+1, len(nums)-1):
                    sabc = sab+nums[c]
                    if sabc+nums[c+1]>target:break
                    if sabc+nums[-1]<target:continue
                    for d in range(c+1, len(nums)):
                        sabcd = sabc+nums[d]
                        if sabcd>target:break
                        if sabcd==target:
                            results.append([nums[a], nums[b], nums[c], nums[d]])
        def cmp(x, y):
            for i in range(4):
                if x[i]<y[i]:return -1
                elif x[i]>y[i]:return 1
            return 0
        results.sort(key=functools.cmp_to_key(cmp))
        finalResults = []
        lastRet = None
        for ret in results:
            if ret!=lastRet:finalResults.append(ret)
            lastRet=ret
        return finalResults
print(Solution().fourSum([-5,-4,-3,-2,-1,0,0,1,2,3,4,5], 0))